/**
 * @projectName algorithm
 * @package PACKAGE_NAME
 * @className PACKAGE_NAME.MergeSort
 */

import util.GeneratorRandomArr;

import java.util.concurrent.CountDownLatch;

/**
 * MergeSort
 * @description 归并排序
 * 原理：二分数组，分开排序，然后归并在一起
 * 时间复杂度：O(N*logN)
 * @author answer_wx
 * @date 2022/6/28 15:06
 * @version 1.0
 */
public class MergeSort {
    // 排序范围，数组角标s-e的范围， 默认e>=s
    public static void process(int[] arr, int s, int e) {
        // 只有一个元素直接返回
        if (s == e) {
            return;
        }
        int mid = s + ((e - s) >> 1);
        // 左右分别排序
        process(arr, s, mid);
        process(arr, mid + 1, e);
        // 使用归并方法，将两边合并在一起
        merge(arr, s, mid, e);
    }


    /**
     * 归并的逻辑
     * 左边数据从左往右 分别与右边数据从左往右比较，
     * 小的话右移一位，并把小的数据放到新的数组里
     * @param arr
     * @param s
     * @param mid
     * @param e
     */
    public static void merge(int[] arr, int s, int mid, int e) {
        // 创建临时数组
        int[] tmp = new int[e - s + 1];
        // 临时数组起始位置
        int i = 0;
        // 左边部分起始下标
        int p1 = s;
        // 右边部分起始下标
        int p2 = mid + 1;
        // 如果p1，p2角标都不越界，则比较两个数据大小
        while (p1 <= mid && p2 <= e) {
            // 临时数组赋值，如果arr[p1] <= arr[p2]，则p1往右移一位，反之亦然
            tmp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 如果右边p2角标越界，则直接从左边赋值
        while (p1 <= mid) {
            tmp[i++] = arr[p1++];
        }
        // 如果左边p1角标越界，则直接从右边赋值
        while (p2 <= e) {
            tmp[i++] = arr[p2++];
        }
        for (int j = 0; j < tmp.length; j++) {
            arr[s + j] = tmp[j];
        }
    }

    public static void main(String[] args) {
        int[] test = GeneratorRandomArr.generator(100, 100);
//        for (int i = 0; i < test.length; i++) {
//            System.out.print(test[i] + ",");
//        }
        System.out.println();
        long start = System.currentTimeMillis();
        process(test, 0, test.length - 1);
        long end = System.currentTimeMillis();
        System.out.printf("时间：%s%n", end - start);
//        for (int i = 0; i < test.length; i++) {
//            System.out.print(test[i] + ",");
//        }
    }
}